洛谷题解 P3958 【奶酪】

发表于 | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 2 分钟

首先这道题要用到以下知识：

并查集、圆与圆的位置关系（可推广到球与球）、空间两点坐标公式

空间两点坐标公式体面给了，这里不讲。

先讲圆与圆的位置关系判定：

如图，从上到下，从左到右依次是：外离，外切，相交，内切，内含

设两圆圆心距离为$d(d>0)$，半径为$r_1$、$r_2$

则有以下关系：

外离：$d>r_1+r_2$

外切：$d=r_1+r_2$

相交：$|r_1-r_2|<d<r_1+r_2$

内切：$d=|r_1-r_2|$

内含：$d<|r_1-r_2|$

此结论可以直接推广至球与球的位置关系。

对于本题，我们只需要考虑外离、相切、相交三种情况，内切和内含可略去（没有意义）。

题中默认$z$轴正方向向上，$x$轴、$y$轴随意（不影响）

我的思路是：

每个球各化为一点，

顶层底层各是一点，

若相切相交即为合并，

最后再验顶底同祖宗。

对于此题，除了用上外离、外切、相交的判定外，还有：

若$z-r<=0$，则该球与底部相交/相切。

若$z+r>=h$，则该球与顶部相交/相切。

贴代码，附解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
	定义底层节点编号为0，顶层节点编号为n+1 
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int n,h,r,fa[1010],T;//fa存父节点
int x[1010],y[1010],z[1010];//你懂得

double dis(double xa,double ya,double za,double xb,double yb,double zb)//套公式
{
	return (double)(sqrt((double)(xa-xb)*(xa-xb)+(double)(ya-yb)*(ya-yb)+(double)(za-zb)*(za-zb)));
}

int find(int s)//注意用了路径压缩
{
	int k=s,t;
	while(k!=fa[k])
	{
		k=fa[k];
	}
	while(s!=fa[s])
	{
		t=s;
		s=fa[s];
		fa[t]=k;
	}
	return k;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&h,&r);
		for(int a=0;a<=n+1;a++)//注意每次要初始化父节点为自己
		{
			fa[a]=a;
		}
		for(int a=1;a<=n;a++)
		{
			scanf("%d%d%d",&x[a],&y[a],&z[a]);
			if(z[a]-r<=0)//底层合并 
			{
				if(find(a)!=find(0))
				{
					fa[find(a)]=find(0);
				}
			}
			if(z[a]+r>=h)//顶层合并 
			{
				if(find(a)!=find(n+1))
				{
					fa[find(a)]=find(n+1);
				}
			}
			for(int b=1;b<a;b++)//洞间合并 
			{
				if(2*r>=dis(x[a],y[a],z[a],x[b],y[b],z[b]))
				{
					if(find(a)!=find(b))
					{
						fa[find(a)]=find(b);
					}
				}
			}
		}
		if(find(0)==find(n+1))//验顶层底层是否连通
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
	return 0;
}

题目详见:https://www.luogu.com.cn/problem/P3958